package algorithm.offer;

import java.util.Arrays;

public class ChongFuShuzu {

  public static void main(String[] args) {
    int[] arr = new int[]{5, 3, 3, 1, 2, 0};

    System.out.println( findDup(arr));
    System.out.println(Arrays.toString(arr));

  }

  public static int findDup(int[] arr) {

    for (int i = 0; i < arr.length; i++) {
      //
      int cur = arr[i];
      while (i != cur) {
        if(cur == arr[cur])
        {
          return cur;
        }
        exchange(arr, i, cur);
        cur = arr[i];
      }
    }
    return 0;
  }

  private static void exchange(int[] arr, int i, int cur) {
    int tmp = arr[i];
    arr[i] = arr[cur];
    arr[cur] = tmp;
  }


}
